package com.sympsel.Optimal_Algorithm_OA;

import org.junit.Test;

import java.util.*;

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}


public class LinkedList {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode list = new ListNode();
        ListNode tail = list;
        int carry = 0, S = 0;
        while (l1 != null || l2 != null || carry > 0) {
            int sum = carry;
            if (l1 != null) {
                sum += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                sum += l2.val;
                l2 = l2.next;
            }
            S = sum % 10;
            carry = sum / 10;
            ListNode newNode = new ListNode(S % 10);
            tail.next = newNode;
            tail = newNode;
        }

        return list.next;
    }

    @Test
    public void test() {
        ListNode l1 = new ListNode(2);
        l1.next = new ListNode(4);
        l1.next.next = new ListNode(3);
        ListNode l2 = new ListNode(5);
        l2.next = new ListNode(6);
        l2.next.next = new ListNode(4);
//        ListNode l1 = new ListNode(3);
//        l1.next = new ListNode(7);
//        ListNode l2 = new ListNode(9);
//        l2.next = new ListNode(2);
        ListNode list = addTwoNumbers(l1, l2);
        for (ListNode node = list; node != null; node = node.next) {
            System.out.print(node.val + " ");
        }
        System.out.println();
    }

    public ListNode swapPairs(ListNode head) {
        ListNode prev = new ListNode();
        prev.next = head;
        ListNode curr = prev.next;
        if (curr == null || curr.next == null) {
            return prev.next;
        }

        ListNode prevCopy = prev;

        ListNode next = curr.next;
        while (next != null) {
            curr.next = next.next;
            next.next = curr;
            prev.next = next;

            prev = curr;
            curr = prev.next;
            if (curr == null) {
                break;
            }
            next = curr.next;
        }
        return prevCopy.next;
    }

    @Test
    public void test2() {
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(2);
        l1.next.next = new ListNode(3);
        l1.next.next.next = new ListNode(4);
        ListNode list = swapPairs(l1);
        for (ListNode node = list; node != null; node = node.next) {
            System.out.print(node.val + " ");
        }
        System.out.println();
    }

    public ListNode detectCycle(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        while (head != null) {
            if (set.contains(head)) {
                return head;
            }
            set.add(head);
            head = head.next;
        }
        return null;
    }

    @Test
    public void test3() {
        ListNode l1 = new ListNode(3);
        l1.next = new ListNode(2);
        l1.next.next = new ListNode(0);
        l1.next.next.next = new ListNode(-4);
        l1.next.next.next.next = l1.next;
        ListNode list = detectCycle(l1);
        System.out.println(list.val);
    }

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null) {
            return null;
        }
        int len = lists.length;
        if (len == 1) {
            return lists[0];
        }

        return merge(lists, 0, len - 1);
    }

    private ListNode merge(ListNode[] lists, int begin, int end) {
        if (begin >= end) {
            return lists[begin];
        }
        int mid = (end - begin) / 2 + begin;

        ListNode leftHead = merge(lists, 0, mid);
        ListNode rightHead = merge(lists, mid + 1, end);

        ListNode ret = new ListNode(0);
        ListNode tail = ret;
        while (leftHead != null && rightHead != null) {
            if (leftHead.val > rightHead.val) {
                tail.next = rightHead;
                rightHead = rightHead.next;
            } else {
                tail.next = leftHead;
                leftHead = leftHead.next;
            }
            tail = tail.next;
        }

        if (leftHead != null) {
            tail.next = leftHead;
        } else {
            tail.next = rightHead;
        }

        return ret.next;
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        if (k == 1) {
            return head;
        }

        int len = 0;
        ListNode p = head;
        while (p != null) {
            len++;
            p = p.next;
        }

        int groupCounts = len / k;
        if (groupCounts == 0) {
            return head;
        }

        p = head;
        int j = len - len % k;
        while (j-- > 0) {
            p = p.next;
        }

        boolean flag = true;
        ListNode newHead = head;
        ListNode curr = head;
        ListNode nextBegin;
        ListNode tail = null; // 初始化为 null

        while (groupCounts-- > 0) {
            ListNode[] listNodes = reverseSingle(curr, k);

            curr = listNodes[0]; // 反转后的头节点
            ListNode tailNode = listNodes[1]; // 反转后的尾节点
            nextBegin = listNodes[2]; // 下一组开始的节点

            if (flag) {
                newHead = curr; // 第一次反转后的头节点是新的头节点
                flag = false;
            } else {
                tail.next = curr; // 将上一组的尾节点连接到当前组的头节点
            }

            tail = tailNode; // 更新尾节点
            curr = nextBegin; // 更新当前节点为下一组的开始节点
        }

        // 当groupCounts == 0时早已返回，所以不会出现tail为null的情况
        tail.next = p; // 将最后一组的尾节点连接到剩余的链表
        return newHead;
    }

    /**
     * @return [newHead, tail, nextBegin]
     */
    private ListNode[] reverseSingle(ListNode beginNode, int k) {
        if (beginNode == null || beginNode.next == null) {
            return new ListNode[]{
                    beginNode, null, null
            };
        }
        ListNode curr = beginNode;

        int kCopy = k;
        while (kCopy-- > 0) {
            curr = curr.next;
        }

        ListNode nextBegin = curr;

        curr = beginNode;
        ListNode next;
        ListNode prev = null;
        kCopy = k;
        while (kCopy-- > 0) {
            next = curr.next;
            curr.next = prev;

            prev = curr;
            curr = next;
        }

        return new ListNode[]{
                prev, beginNode, nextBegin
        };
    }

    @Test
    public void test4() {
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
        ListNode list = reverseKGroup(head, 2);
        for (ListNode node = list; node != null; node = node.next) {
            System.out.print(node.val + " ");
        }
    }
}
